/****************************************************************************
 * Elisa 1.0                                                                *
 *--------------------------------------------------------------------------*
 * Author: Laurent Granvilliers, Vincent Sorin                              *
 * Copyright (c) 2004 Laboratoire d'Informatique de Nantes Atlantique       *
 *--------------------------------------------------------------------------*
 * Elisa is distributed WITHOUT ANY WARRANTY. Read the associated           *
 * COPYRIGHT file for more details.                                         *
 *--------------------------------------------------------------------------*
 * elisa_variable.h															*
 ****************************************************************************/

#ifndef _elisa_variable_h_
#define _elisa_variable_h_ 1

#include <set>
#include <vector>
#include <string>
#include <stdlib.h>
#include <iostream>
#include <map>
#include <memory>
#include <boost/shared_ptr.hpp>

#include "elisa_defs.h"
#include "elisa_domain.h"
#include "elisa_observer.h"
#include "elisa_heap.h"

NAMESPACE_ELISA

// forward declaration
class SearchTree;
class Variable;
class VariableImpl;


//--------------------------------------------------------------------------
// class VariableImplCmp
//--------------------------------------------------------------------------

/**
 * @ingroup Variable
 * @class VariableImplCmp
 * @brief base class for comparison between variables
 *
 * It is the base class for Comparator between variables.
 * You must implement inf function. For more clearness,
 * call your comparator : Type1Type2Cmp
 */
class VariableImplCmp
{
public:
	//Exception class
	class WrongType { };

	/**
 	 * @brief it compares two type of variable
 	 * @param v1 the first variable
 	 * @param v2 the second variable
 	 * @return true if v1 < v2, else otherwise
 	 */
	virtual bool best(VariableImpl *v1,
	                  VariableImpl *v2) = 0;
};

//--------------------------------------------------------------------------
// class VariableImplCmpChooser
//--------------------------------------------------------------------------

typedef boost::shared_ptr<VariableImplCmp> VariableImplCmpPtr;

/**
 * @ingroup Variable
 * @class mapCmp
 * @brief map of VariableImplCmp. The key is the concatenation of the two types compared
 */
typedef std::map<std::string, VariableImplCmpPtr, ltstr > MapCmp;


/**
 * @ingroup Variable
 * @class VariableImplCmpChooser
 * @brief Class for the management of the map of VariableImplCmp
 */
class VariableImplCmpChooser
{
public:

	~VariableImplCmpChooser()
	{
		//clear();
	}

	/**
 	 * @brief insert a VariableImplCmp into the map
 	 * the both string are used as a key to index the comparator in the map
 	 * @param t1 first type that can be compared
 	 * @param t2 second type that can be compared
 	 * @param v pointer to the comparator
 	 */
	static void insert(std::string t1, std::string t2, VariableImplCmp *v)
	{
		m_cmpMap[t1 + t2] = VariableImplCmpPtr(v);
	}


	/**
 	 * @brief return a VariableImplCmp given the two types of VariableImpl to compare
 	 * @param t1 type of the first VariableImpl
 	 * @param t2 type of the second VariableImpl
 	 * @return a pointer to a comparator between VariableImpl of type t1 and t2, null
 	 * if that comparator doesn't exist
 	 */
	static VariableImplCmp *get(std::string t1, std::string t2)
	{
		return m_cmpMap[t1 + t2].get();
	}


	/**
 	 * @brief empties the map
 	 * @post the map is empty and all VariableImplCmp have been deleted
 	 */
	static void clear()
	{
		/*
		MapCmp::iterator it;
		for (it = m_cmpMap.begin(); it != m_cmpMap.end(); ++it)
			delete (*it).second;
		*/
		m_cmpMap.clear();
	}

private:
	/**
 	 *@var map used to recover a comparator
 	 */
	static MapCmp m_cmpMap;
};


//typedef VariableImpl *VariablePtr;
typedef boost::shared_ptr<VariableImpl> VarImplPtr;

struct VariableSetCmp 
{
	bool operator()(const VarImplPtr x, const VarImplPtr y)
	{
		//return x > y;
		return x.get() > y.get();
	}
};

/**
 * @ingroup Variable
 * @class SetVar
 * @brief Set of VariableImpl using the stl set class
 */
typedef std::set<VarImplPtr, VariableSetCmp> VarImplSet;


/**
 * @ingroup Variable
 * @class VecVar
 * @brief Vector of VariableImpl using the stl vector class
 */
typedef std::vector<VarImplPtr> VarImplVector;


/**
 * @ingroup Variable
 * @class MapVar
 * @brief Map of VariableImpl using the stl vector class
 */
typedef std::map<long, VariableImpl *, ltlong> VarImplMap;


/**
 * @class BTBoxIndex
 * This class is an index that permits to retrieve the information contained in
 * a box
 */
class BTBoxIndex
{
	/** Public methods: */
public:
	/**
 	 * Constructor
 	 */
	BTBoxIndex()
	{
	}

	/**
 	 * Get the value contained in the box
 	 * @return a pointer to the begin of the box
 	 */
	char *getValue()
	{
		return m_value;
	}

	/**
 	 * Initialize the box
 	 * @param size the size of the value contained in the box
 	 * @param value a pointer to the begin of the memory allocated for this box
 	 */
	void init(size_t size, char *value)
	{
		m_size = size;
		m_value = m_last = value;
	}

	/**
 	 * Getter for the first free bytes in the box (back of the box)
 	 * @return a pointer to the back of the box
 	 */
	char *getLast()
	{
		return m_last;
	}

	/**
 	 * Get the size of the box
 	 * @return the size of the box
 	 */
	size_t getSize()
	{
		return m_size;
	}

	/**
 	 * Get the number of the box in the heap
 	 * @return the number of the box
 	 */
	int getNum()
	{
		return m_num;
	}

	/**
 	 * Set the begin of the memory space of the box
 	 * @param value the begin of the memory space
 	 */
	void setValue(char *value)
	{
		m_value = value;
	}

	/**
 	 * Setter for the size
 	 * @param size the nex size of the box
 	 */
	void setSize(size_t size)
	{
		m_size = size;
	}

	/**
 	 * Setter for the back of the box
 	 * @param last pointer the first free bytes of the box
 	 */
	void setLast(char *last)
	{
		m_last = last;
	}

	/**
 	 * Setter for the number of the box
 	 * @param num number of the box in the heap
 	 */
	void setNum(int num)
	{
		m_num = num;
	}

	/**
 	 * allocate memory in the box and saves the domain
 	 * @param n the size of the domain to save
 	 * @param d the domain to save
 	 * @return the offset between the beginning of the box and the domain
 	 */
	int allocate(size_t n, const Domain & d)
	{
		int result = m_last - m_value;
		memcpy(m_last, &d, n);
		m_last = m_last + n;
		return result;
	}

	/**
 	 * Get the value of the domain given the offset
 	 * @param int the offset
 	 * @return a pointer to the memory space where the  domain is stored
 	 */
	void *valueDomain(int adr)
	{
		return static_cast<void *>(m_value + adr);
	}

private:
	/**
 	 * @var pointer to the begin of the box
 	 */
	char *m_value;

	/**
 	 * @var size of the box
 	 */
	size_t m_size;

	/**
 	 * @var pointer to the firts free bytes in the box
 	 */
	char *m_last;

	/**
 	 * @var number of the box
 	 */
	int m_num;
};


/**
 * @class ChangeHeap
 * The class is the heap where domain of splitted variables are stored
 */

class ChangeHeap
{
	/** Public methods: */
public:
	/// Exception class
	class ChangeHeapOverflow { };

	/**
 	 * Constructor
 	 * @param size the size of the heap
 	 * @param max the maximum number of box in the heap
 	 */
	ChangeHeap(const long size = DefaultHeapSize,
	           const long max = DefaultMaxBox)
	{
		m_value = new char[m_maxSize = size];
		m_index = new BTBoxIndex[m_maxBox = max];
		m_index[0].setValue(m_value);
		m_index[0].setSize(0);
		m_numBox = 0;
	}

	/**
 	 * Destructor
 	 */
	~ChangeHeap()
	{
		delete[] m_value;
		delete[] m_index;
	}

	/**
 	 * add a box in the heap
 	 * @param size the size of the box
 	 */
	int addBox(size_t size)
	{
		if (m_numBox + 1 < m_maxBox) {
			//if (m_index[m_numBox - 1].getValue() + m_index[m_numBox - 1].getSize() + size < m_value + m_maxSize) {
			if (m_index[m_numBox].getValue() + m_index[m_numBox].getSize() + size < m_value + m_maxSize) {
				m_numBox++;
				m_index[m_numBox].init(size, m_index[m_numBox - 1].getValue() + m_index[m_numBox - 1].getSize());
				return m_numBox;
			} else {
				throw ChangeHeapOverflow();
			}
		} else {
			throw ChangeHeapOverflow();
		}
	}

	/**
 	 * allocate n bytes at the end of the last box
 	 * @param n the number of bytes to be allocated
 	 * @param d the domain to store
 	 * @ return the key to find th e
 	 */
	int allocate(size_t size, const Domain & d)
	{
		return m_index[m_numBox].allocate(size, d);
	}

	/**
 	 * Return the value of a domain
 	 * @param n the key to know the place of the domain in the box
 	 * @param b the box in which is the domain
 	 *
 	 */
	void *getDomain(long numb, long n)
	{
		return m_index[numb].valueDomain(n);
	}

	/**
 	 * Remove a box from the heap
 	 * @param b the box to remove
 	 */
	void discardBox(long numb)
	{
		m_numBox = numb - 1;
	}

private:
	/**
 	 * @var the vector of box's indexes
 	 */
	BTBoxIndex *m_index;

	/**
 	 * @var pointer to the begin of the heap
 	 */
	char *m_value;

	/**
 	 * @var maximum size of the heap
 	 */
	long m_maxSize;

	/**
 	 * @var max number of boxe in the heap
 	 */
	long m_maxBox;

	/**
 	 * @var number of boxes in the heap
 	 */
	long m_numBox;

	static const long DefaultHeapSize;     // default size of the heap
	static const long DefaultMaxBox;       // default max number of boxes during search
};



/**
 * @class DomainChange
 * this class is used to keep trace of the changement of variable's domain
 */
class DomainChange
{
	/** Public methods: */
public:
	/**
 	 * Constructor
 	 * @param numBox the number of the box where the domain is stored
 	 * @param indexDomainBT index the retreive the value of the domain (offset)
 	 */
	DomainChange(long numBox, long indexDomainBT)
	{
		m_numBox = numBox;
		m_indexDomainBT = indexDomainBT;
		m_nref = 0;
	}

	/**
 	 * Reference couting
 	 */
	int addRef()
	{
		return ++m_nref;
	}

	/**
 	 * Reference couting
 	 */
	int delRef()
	{
		if (--m_nref == 0)
			delete this;
		return m_nref;
	}

	/**
 	 * Reference couting
 	 */
	int ref()
	{
		return m_nref;
	}

	/**
 	 * Getter for the index of the domain
 	 * @return the offset to found the value of the domain
 	 */
	long getIndexDomainBT()
	{
		return m_indexDomainBT;
	}

	/**
 	 * Getter for the number of the box
 	 * @return the number of the box where the domain is stored
 	 */
	long getNumBox()
	{
		return m_numBox;
	}

protected:
	/**
 	 * @var indexDomain of the domain in the btSearchSpace
 	 */
	long m_indexDomainBT;

	/**
 	 * @var number of object using this*
 	 */
	int m_nref;

	/**
 	 * @var number of the box where the domain is stored
 	 */
	long m_numBox;
};

class Node;

//typedef boost::shared_ptr<Node> NodePtr;

typedef std::set<Node *> NodeSet;

//--------------------------------------------------------------------------
// class SearchTree
//--------------------------------------------------------------------------
/**
 * @ingroup Variable
 * @class SearchTree
 * @brief SearchTree = (domains), i.e., bisectable objects
 * FIX utiliser le pattern strategie pour goNext de maniere a faire un bt intelligent et un next intelligent
 */
class SearchTree
{
public:
	void setBFS()
	{
		m_dfs = false;
		m_heap->setBFS();
	}

	void setDFS()
	{
		m_dfs = true;
		m_heap->setDFS();
	}

	/**
 	 * @brief  Constructor
 	 * @param heap the used to store domains. If no one is given, it builds a new one
 	 */
	SearchTree(Heap *heap = 0, ChangeHeap *ChangeHeap = 0);

	/**
 	 * @brief Destructor
 	 * @post the heap has been deleted
 	 */
	~SearchTree();

	/**
 	 * @brief Insertion of a VariableImpl in the model
 	 * @param v the VariableImpl to add
 	 */
	void add(VariableImpl *v);


	VariableImpl *getVariable(long indexDomain);


	/// @name Iterators over the set of variables
	//@{
	VarImplMap::iterator beginVar()
	{
		return m_varMap.begin();
	}

	VarImplMap::const_iterator beginVar() const
	{
		return m_varMap.begin();
	}

	VarImplMap::iterator endVar()
	{
		return m_varMap.end();
	}

	VarImplMap::const_iterator endVar() const
	{
		return m_varMap.end();
	}
	//@}

	/**
 	 * @brief Access to the heap
 	 * @return a pointer to the heap
 	 */
	/*
	Heap *heap() const
	{
		return m_heap;
	}
	*/

	/**
 	 * Allocation of a new domain of size n at the end of the heap
 	 * @return the index of domain in the heap
 	 */
	long allocate(size_t n) throw (Heap::HeapDomainOverflow)
	{
		return m_heap->allocate(n);
	}

	/**
 	 * Allocation of a new domain of type D at the end of the heap
 	 * @return the index of domain in the heap
 	 */
	template <class D>
	long allocate() throw (Heap::HeapDomainOverflow)
	{
		return allocate(sizeof(D));
	}

	/**
 	 * @brief Can tell if the current box is splittable
 	 * @return true if the current box is splittable
 	 */
	bool isSplittable() const;

	/**
 	 * tells if the heap is empty
 	 * @return true if numBox()==0
 	 */
	bool isEmpty() const;

	/**
 	 * Return a box which is just a point in the current box.
 	 * The extraction of an element from each domain is done by
 	 * the method Variable::toPoint(Box*)
 	 */
	Box *toPoint() const;

	/**
 	 * Prepare the SearchTree for reduction step
 	 * If dfs is true, it makes a copy of the current box,
 	 * nothing otherwise
 	 */
	void prepareReduce();

	/**
 	 * Return a copy of the current box
 	 * @return a box with the same value of the current box
 	 */
	Box *copyBox() const
	{
		return m_heap->copyBox();
	}

	/**
 	 * Go back in the tree
 	 */
	inline bool discardBox();

	/**
 	 * @brief Modification of the current domain
 	 * @param dom the new domain of the variable
 	 */
	void setDomain(long adr, size_t size, const void *dom) const
	{
		m_heap->setDomain(adr, size, dom);
	}

	/**
 	 * @brief Modification of the current domain
 	 * @param dom the new domain of the variable
 	 */
	template<class D>
	void setDomain(long adr, const D & dom) const
	{
		m_heap->setDomain<D>(adr, dom);
	}

	/**
 	 * @brief Modification of the domain in a box
 	 * @param dom the new domain of the variable
 	 */
	template<class D>
	void setDomain(long adr, Box *b, const D & dom) const
	{
		m_heap->setDomain<D>(adr, b, dom);
	}

	/**
 	 * Return the current domain
 	 * @return the domain of the Variable
 	 */
	template<class D>
	const D & const_domain(long adr) const
	{
		return m_heap->const_domain<D>(adr);
	}

	/**
 	 * Return the domain from a box
 	 * @return the domain from a box
 	 */
	template<class D>
	const D & const_domain(long adr, Box *b) const
	{
		return m_heap->const_domain<D>(adr, b);
	}

	/**
 	 * Return a pointer to the current domain
 	 * @return a pointer to the domain of the Variable
 	 */
	template<class D>
	D *domain(long adr)
	{
		return m_heap->domain<D>(adr);
	}

	/**
 	 * Return a pointer to the domain from a box
 	 * @return a pointer to the domain from a box
 	 */
	template<class D>
	D *domain(long adr, Box *b)
	{
		return m_heap->domain<D>(adr, b);
	}

	/**
 	 * The variable domain is split into dom1 and dom2
 	 * @param dom1 first part of the split domain
 	 * @param dom2 second part of the split domain
 	 */
	template<class D>
	void splitBox(long adr,
	              const D & dom1,
	              const D & dom2);

	/**
 	 * The variable domain is split in n domains
 	 */
	template<class D>
	void splitBox(long adr,
	              const D *doms,
	              int n);

	/**
 	 * The variable domain is reduce to the domain dom
 	 */
	template<class D>
	void reduce(long adr, const D & dom);

	/**
 	 * Getter for the root node
 	 * @return the root node
 	 */
	Node *getRoot()
	{
		return m_dfs ? m_root : 0;
	}

	/**
 	 * Getter for the current node
 	 * @return the current node
 	 */
	Node *getCurrent()
	{
		return m_dfs ? m_current : 0;
	}

	/**
 	 * Setter for the current node
 	 * @param the current node
 	 */
	void setCurrent(Node *current)
	{
		m_current = current;
	}

	/**
 	 * Setter for the roo node
 	 * @param the root node
 	 */
	void setRoot(Node *root)
	{
		m_root = root;
	}

	/**
 	 * Getter for the boxes' heap
 	 * @return the Heap
 	 */
	Heap *getHeap()
	{
		return m_heap.get();
	}

	/**
 	 * Getter for the domains' heap
 	 * @return the ChangeHeap
 	 */
	ChangeHeap *getChangeHeap()
	{
		return m_changeHeap.get();
	}

protected:
	/**
 	 * @name Splitting methods for Depth-First Search
 	 * The domain at address adr is split in two domains dom1 and dom2.
 	 * The current box is removed.
 	 * Two boxes are added at the top of the heap in the following order:
 	 *   <ul>
 	 *   <li> a copy of the old current box where the domain at address
 	 *        adr takes value dom2;
 	 *   <li> a copy of the old current box where the domain at address
 	 *        adr takes value dom1. This box becomes the current box.
 	 *   </ul>
 	 */
	template <class D>
	void splitBoxToBack(long adr,
	                    const D & dom1,
	                    const D & dom2)
	{
		m_heap->splitBoxToBack<D>(adr, dom1, dom2);
	}

	/// Splitting methods for Breadth-First Search
	template <class D>
	void splitBoxToFront(long adr,
	                     const D & dom1,
	                     const D & dom2)
	{
		m_heap->splitBoxToFront<D>(adr, dom1, dom2);
	}

	/**
 	 * @var The heap ; top of the heap = current box
 	 */
	std::auto_ptr<Heap> m_heap;

	/**
 	 * @var The set of variables of the model
 	 */
	VarImplMap m_varMap;

	/**
 	 * @var true if DFS search, false if BFS
 	 */
	bool m_dfs;

	/**
 	 * @var the root of the tree
 	 */
	Node *m_root;

	/**
 	 * @var the current explored node
 	 */
	Node *m_current;

	/**
 	 * @var the domains' heap
 	 */
	std::auto_ptr<ChangeHeap> m_changeHeap;

private:
	/// Copy protection
	SearchTree & operator=(const SearchTree & m) {}
	SearchTree (const SearchTree & m) {}
};


/**
 * @class Node
 * @brief node of the search tree
 */
class Node
{
public:
	/**
 	 * Constructor
 	 * @param tree the tree in which the node is
 	 * @param father the father node of this
 	 */
	Node(SearchTree *tree, Node *father)
	{
		m_father = father;
		m_tree = tree;
		m_explored = false;
		m_unexploredChildren = new Node *[m_maxUnexploredChildren = 2];
		m_numUnexploredChildren = 0;
		m_children = new Node *[m_maxChildren = 2];
		m_numChildren = 0;
	}

	/**
 	 * Go back to the father
 	 */
	virtual bool goBack() = 0;

	/**
 	 * Go from the father to this node
 	 */
	virtual void goHere() = 0;

	/**
 	 * go to nth children of this node
 	 * @pre this must be the current node in the exploration tree
 	 * @param n the child to go
 	 */
	bool goChild(Node *n);

	/**
 	 * Go back to the father
 	 */
	virtual Node *goBack(Box *b) = 0;

	/**
 	 * Go from the father to this node
 	 */
	virtual void goHere(Box *b) = 0;

	/**
 	 * go to nth children of this node
 	 * @pre this must be the current node in the exploration tree
 	 * @param n the child to go
 	 */
	bool goChild(Node *n, Box *b);

	/**
 	 * Destructor
 	 */
	virtual ~Node()
	{
		for (unsigned int i = 0; i < m_numChildren; ++i) {
			delete m_children[i];
		}
		delete m_children;
		delete m_unexploredChildren;
	}

	/**
 	 * Splits the exploration tree
 	 * @pre this must be the current node in the exploration tree
 	 * @param indexDomain the index to find the domain in the boxes' heap
 	 * @param size the size of the domain
 	 * @param dom1 the domain of the first branch
 	 * @param dom2 the domain of the second branch
 	 * @param numb the number of the box in the domains' heap
 	 * @param before the changement to go back to the father
 	 */
	void split(long indexDomain, size_t size, const Domain & dom1, const Domain & dom2, long numb, DomainChange *before);

	/**
 	 * Save the reduction of a domain
 	 * @pre this must be the current node in the exploration tree
 	 * @param indexDomain the index to find the domain in the boxes' heap
 	 * @param size the size of the domain
 	 * @param dom1 the new value of the domain
 	 * @param numb the number of the box in the domains' heap
 	 * @param before the changement to go back to the father
 	 */
	void reduce(long indexDomain, size_t size, const Domain & dom1, long numb, DomainChange *before);

	/**
 	 * make a copy of the current box
 	 * that method is usefull when a reduction step will reduce many domains
 	 */
	void prepareLargeReduce();

	/**
 	 * Splits the exploration tree
 	 * @pre this must be the current node in the exploration tree
 	 * @param indexDomain the index to find the domain in the boxes' heap
 	 * @param size the size of the domain
 	 * @param dom the vector of domains of the branches
 	 * @param the number of branches
 	 * @param numb the number of the box in the domains' heap
 	 * @param before the changement to go back to the father
 	 */
	void split(long indexDomain, size_t size, const Domain *dom, int n, long numb, DomainChange *before);

	/**
 	 * Return the array of unexplored children
 	 */
	Node **getUnexploredChildren()
	{
		return m_unexploredChildren;
	}

	/**
 	 * Return the number of unexplored children
 	 */
	unsigned int getNumUnexploredChildren()
	{
		return m_numUnexploredChildren;
	}

	/**
 	 * Return the array of children
 	 */
	Node **getChildren()
	{
		return m_children;
	}

	/**
 	 * Return the number of children
 	 */
	unsigned int getNumChildren()
	{
		return m_numChildren;
	}

	/**
 	 * Go up in the exploration tree to parent
 	 * @pre this must be the current node in the exploration tree
 	 * @param parent the node to go up
 	 */
	void goAncestor(Node *parent);

	/**
 	 * Return true if the node has a father
 	 */
	bool hasFather()
	{
		return m_father != 0;
	}

	Node *father()
	{
		return m_father;
	}

	/**
 	 * Called when this has been explored
 	 */
	void hasBeenExplored()
	{
		if (m_father != 0)
			m_father->exploredChild(this);

		m_explored = true;
	}

	/**
 	 * To know if this has been explored
 	 * @return true if this has been explored
 	 */
	bool isExplored()
	{
		return m_explored;
	}

protected:
	/**
 	 * That method is called when the child n has been explored
 	 */
	void exploredChild(Node *n)
	{
		this->eraseUnexploredChild(n);
	}

	/**Compositions: */
	///@var the box
	long m_numBox;

	///@var the set of children
	Node **m_children;

	///@var number of children in the array
	unsigned int m_numChildren;

	///@var size of the array of children
	unsigned int m_maxChildren;

	///@var the set of unexplored children
	Node **m_unexploredChildren;

	///@var number of unexplored children in the array
	unsigned int m_numUnexploredChildren;

	///@var size of the array of unexplored children
	unsigned int m_maxUnexploredChildren;

	/**
 	 * Add the node n in the array of unexplored children
 	 */
	void addUnexploredChild(Node *n)
	{
		if (m_maxUnexploredChildren < m_numUnexploredChildren) {
			Node **temp = m_unexploredChildren;
			m_maxUnexploredChildren += 2;
			m_unexploredChildren = new Node *[m_maxUnexploredChildren];
			memcpy(m_unexploredChildren, temp, sizeof(temp));
			delete temp;
		}
		m_unexploredChildren[m_numUnexploredChildren] = n;
		m_numUnexploredChildren++;
	}

	/**
 	 * Add the node n in the array of children and unexplored children
 	 */
	void addChild(Node *n)
	{
		addUnexploredChild(n);
		if (m_maxChildren < m_numChildren) {
			Node **temp = m_children;
			m_maxChildren += 2;
			m_children = new Node *[m_maxChildren];
			memcpy(m_children, temp, sizeof(temp));
			delete temp;
		}
		m_children[m_numChildren] = n;
		m_numChildren++;
	}

	/**
 	 * erase the node n from the array of unexplored children
 	 */
	void eraseUnexploredChild(Node *n)
	{
		unsigned int i = 0;
		while ((m_unexploredChildren[i] != n) && (i != m_numUnexploredChildren - 1)) ++i;

		for (unsigned int a = i; a < m_numUnexploredChildren - 1; ++a)
			m_unexploredChildren[a] = m_unexploredChildren[a + 1];

		m_numUnexploredChildren--;
	}

	//@var the father
	Node *m_father;

	/**
 	 * @var true if this has been explored
 	 */
	bool m_explored;

	/**
 	 * @the exploration tree
 	 */
	SearchTree *m_tree;
};


/**
 * @class ReduceNode
 * node to handle a reduction of an entire box
 */
class ReduceNode : public Node
{
public:
	/**
 	 * Constructor
 	 */
	ReduceNode(SearchTree *tree, Node *father) : Node(tree, father)
	{
	}

	/**
 	 * Go back to the father
 	 */
	bool goBack()
	{
		m_tree->getHeap()->discardBox();
		m_tree->setCurrent(this->m_father);
		for (unsigned int i = 0; i < m_numChildren; ++i)
			delete m_children[i];

		m_numChildren = 0;
		return !m_tree->getHeap()->isEmpty();
	}

	/**
 	 * Go from the father to this
 	 */
	void goHere()
	{
		m_numBox = m_tree->getHeap()->copyCurrentBoxToBack();
		m_tree->setCurrent(this);
	}


	/**
 	 * Go back to the father
 	 */
	Node *goBack(Box *b)
	{
		delete b;
		b = m_tree->getHeap()->copyBox(m_numBox - 1);
		return m_father;
	}

	/**
 	 * Go from the father to this
 	 */
	void goHere(Box *b)
	{
	}

private:
	long m_numBox;
};


/**
 * @class SplitNode
 * This is a node of a split in the exploration tree
 */
class SplitNode : public Node
{
	/** Public methods: */
public:
	/**
 	 * Constructor
 	 * @param tree the exploration tree
 	 * @param indexDomain the index to find the domain in the boxes' heap
 	 * @param change the DomainChange to go from the father to this
 	 * @param before the change to go from this to the father
 	 * @param father the father of this node
 	 */
	SplitNode(SearchTree *tree, long indexDomain, size_t size, DomainChange *change, DomainChange *before, Node *father) : Node(tree, father)
	{
		m_indexDomain = indexDomain;
		m_size = size;
		m_change = change;
		m_before = before;
		m_before->addRef();
		m_numb = -1;
	}

	/**
 	 * Constructor
 	 * @param tree the exploration tree
 	 */
	SplitNode(SearchTree *tree) : Node(tree, 0)
	{
		m_indexDomain = 0;
		m_size = 0;
		m_change = 0;
		m_before = 0;
		m_tree = tree;
		m_numb = -1;
		m_explored = false;
	}

	/**
 	 * destructor
 	 */
	~SplitNode()
	{
		if (m_change != 0)
			delete m_change;

		if (m_before != 0)
			m_before->delRef();
	}

	/**
 	 * This function goes up in the tree
 	 * @pre this must be the current node in the exploration tree
 	 * @result : if the current node is the root, it returns false
 	 */
	bool goBack()
	{
		if (m_father != 0) {
			m_explored = true;

			m_tree->getHeap()->setDomain(m_indexDomain, m_tree->getChangeHeap()->getDomain(m_before->getNumBox(), m_before->getIndexDomainBT()), m_size);

			// if this node has no child, it has no box in the heap
			if (m_numb != -1)
				m_tree->getChangeHeap()->discardBox(m_numb);

			m_tree->setCurrent(m_father);
			for (unsigned int i = 0; i < m_numChildren; ++i)
				delete m_children[i];

			m_numChildren = 0;

			return(m_father->hasFather());
		}
		return false;
	}


	/**
 	 * This method makes the changement to go from this to its father in the box b
 	 * the exploration tree, the Heap and the ChangeHeap are unchanged
 	 * @param b the box where the domain must be changed
 	 * @return the father of this
 	 */
	Node *goBack(Box *b)
	{
		m_tree->getHeap()->setDomain(m_indexDomain, m_tree->getChangeHeap()->getDomain(m_before->getNumBox(), m_before->getIndexDomainBT()), m_size, b);
		return m_father;
	}

	/**
 	 * Apply the changement in the boxes' heap to go to this
 	 * @pre this->_father must be the current node in the exploration tree
 	 */
	void goHere()
	{
		m_tree->getHeap()->setDomain(m_indexDomain, m_tree->getChangeHeap()->getDomain(m_change->getNumBox(), m_change->getIndexDomainBT()), m_size);
		m_tree->setCurrent(this);
	}

	/**
 	 * Apply the changement in the boxes' heap to go to this
 	 * @pre this->_father must be the current node in the exploration tree
 	 */
	void goHere(Box *b)
	{
		m_tree->getHeap()->setDomain(m_indexDomain, m_tree->getChangeHeap()->getDomain(m_change->getNumBox(), m_change->getIndexDomainBT()), m_size, b);
	}

	/**
 	 * This method the Variable that has been splitted
 	 * @return the splitted VariableImpl
 	 */
	VariableImpl *getVariableImplementation();

protected:

	/// @var the change to go from the father to this
	DomainChange *m_change;

	/// @var the change to go from this to the father
	DomainChange *m_before;

	/**
 	 * @var indexDomain of the domain in the SearchTree
 	 */
	long m_indexDomain;

	/**
 	 * @var the size of the domain
 	 */
	size_t m_size;

	/**
 	 * the number of the box in the domains' heap
 	 */
	int m_numb;
};


//--------------------------------------------------------------------------
// class VariableImpl
//--------------------------------------------------------------------------

/**
 * @ingroup Variable
 * @class VariableImpl
 * @brief Internal Representation of a symbolic variable
 */
class VariableImpl : public Subject
{
public:
	/**
 	 * Constructor
 	 * @param var the symbolic Variable corresponding to this
 	 */
	VariableImpl(Variable *var, SearchTree *searchTree, size_t n, int priority = 0);

	/**
 	 * Destructor
 	 */
	virtual ~VariableImpl();

	/// @name Comparisons
	//@{
	virtual bool operator==(const VariableImpl & v) const
	{
		return this == (&v);
	}

	virtual bool operator!=(const VariableImpl & v) const
	{
		return this != (&v);
	}

	bool best(VarImplPtr v)
	{
		VariableImplCmp *vcmp = VariableImplCmpChooser::get(this->getType(), v->getType());
		if (vcmp == 0)
			return true;
		else
			return vcmp->best(this, v.get());
	}

	//@}

	/// @name Base class's virtual methods
	//@{

	/**
 	 * @brief To know the precise type of the Variable
 	 * @return a string given the name of the type
 	 */
	virtual std::string getType() const = 0;

	/**
 	 * Method to know if the domain is splittable
 	 * @return true if the variable domain can be split used during search.
 	 */
	virtual bool isSplittable() const = 0;

	/**
 	 * Split of the current box
 	 */
	virtual void split() const = 0;

	/**
 	 * Split of the current box
 	 */
	virtual void split3() const
	{
		// TODO
	}

	/**
 	 * @brief reduce the current domain to a point in b
 	 * @post The domain of THIS in b := a point in b
 	 */
	virtual void toPoint(Box *b) const = 0;

	/**
 	 * Return the size of the variable domain
 	 * @return the size in memory of the domain
 	 */
	virtual size_t size() const = 0;

	/**
 	 * Set the domain of the symbolic representation
 	 * Called when a solution is computed
 	 * @param d the solution computed
 	 */
	virtual void updateSymbolicDomain() const = 0;
	//@}

	/// Getter for searchSpace
	//@{
	SearchTree *getSearchTree() const
	{
		return m_searchTree;
	}

	//@}

	/// Getter and setter for Sympbolic Variable

	//@{
	Variable *getSymbolicRep() const
	{
		return m_symbolicRep;
	}

	void setSymbolicRep(Variable *value)
	{
		m_symbolicRep = value;
	}
	//@}

	/**
 	 * @brief gives the priority of the subject
 	 * inherited from Subject
 	 * @return the priority
 	 */
	const int & getPriority() const
	{
		return m_priority;
	}

	const long & getIndexDomain() const
	{
		return m_indexDomain;
	}

protected:
	/**
 	 * @brief Modification of the current domain
 	 * @param dom the new domain of the variable
 	 */
	template<class D>
	void setDomain(const D & dom) const
	{
		m_searchTree->setDomain<D>(m_indexDomain, dom);
	}

	/**
 	 * @brief Modification of the domain in a box
 	 * @param dom the new domain of the variable
 	 */
	template<class D>
	void setDomain(const D & dom, Box *b) const
	{
		m_searchTree->setDomain<D>(m_indexDomain, b, dom);
	}

	/**
 	 * Return the current domain
 	 * @return the domain of the Variable
 	 */
	template<class D>
	const D & const_domain() const
	{
		return m_searchTree->const_domain<D>(m_indexDomain);
	}

	/**
 	 * Return the domain from a box
 	 * @return the domain from a box
 	 */
	template<class D>
	const D & const_domain(Box *b) const
	{
		return m_searchTree->const_domain<D>(m_indexDomain, b);
	}

	/**
 	 * Return a pointer to the current domain
 	 * @return a pointer to the domain of the Variable
 	 */
	template<class D>
	D *domain()
	{
		return m_searchTree->domain<D>(m_indexDomain);
	}

	/**
 	 * Return a pointer to the domain from a box
 	 * @return a pointer to the domain from a box
 	 */
	template<class D>
	D *domain(Box *b)
	{
		return m_searchTree->domain<D>(m_indexDomain, b);
	}

	/**
 	 * The variable domain is split into dom1 and dom2
 	 * => creation of one boxe in the heap
 	 * @param dom1 first part of the split domain
 	 * @param dom2 second part of the split domain
 	 */
	template<class D>
	void splitBox(const D & dom1,
	              const D & dom2) const
	{
		m_searchTree->splitBox<D>(m_indexDomain, dom1, dom2);
	}

	template<class D>
	void splitBox(const D *doms,
	              const int n) const
	{
		m_searchTree->splitBox<D>(m_indexDomain, doms, n);
	}

	// copy protection
	// @brief Copy constructor
	VariableImpl(const VariableImpl & right) : Subject(right)
	{
	}
	VariableImpl & operator=(const VariableImpl & right)
	{
	}


	// @var index of the domain of the variable in the heap
	long m_indexDomain;

	// @var pointer to the symbolic variable
	// used to update the value of the domain
	Variable *m_symbolicRep;

	// @var searchSpace use for computation
	SearchTree *m_searchTree;

	// @var priority of the type of variable for search
	int m_priority;

	size_t m_size;
};


//--------------------------------------------------------------------------
// class Variable
//--------------------------------------------------------------------------

/** 
 * @ingroup Variable
 * @class Variable
 * @brief Base class for constrained variables.
 *
 * <UL>
 * <LI> Each variable has a name, a domain and a list of listeners
 *   that must be checked when domain modifications happen.
 * <LI> Each variable belongs to one search space.
 * </UL>
 * @see SearchTree
 */
class Variable
{
public:
	/**
 	 * @brief Constructor
 	 *
 	 * This constructor builds a symbolic variable
 	 * @param factory Factory which will build the implementation of the symbolic variable
 	 * @param dom the domain of the variable
 	 * @param the name of the variable
 	 */
	Variable(Domain *domain = 0, const std::string & name = "");

	/**
 	 * @brief Destructor
 	 */
	virtual ~Variable();

	/**
 	 * @brief print the value of the domain in a stream
 	 * @var os the output stream
 	 */
	virtual void printDomain(std::ostream & os) const
	{
		this->m_domain->print(os);
	}

	/**
 	 * @brief getter for name
 	 * @return the name of the variable
 	 */
	const std::string getName() const
	{
		return m_name;
	}

	/**
 	 * @brief getter for the domain
 	 * @return the domain of the variable
 	 */
	Domain *getDomain() const
	{
		return m_domain;
	}

	/**
 	 * @brief setter for the domain
 	 * @param value the new domain of the variable
 	 */
	void setDomain(Domain *value)
	{
		m_domain = value;
	}

	/**
 	 * @brief getter for internal representation
 	 * @return the variable implementation
 	 */
	VarImplPtr getImplementation() const
	{
		return m_implementation;
	}

	/**
 	 * @brief function to print the variable in a stream
 	 * @param os the stream
 	 */
	virtual void print(std::ostream & os) const
	{
		os << m_name;
	}

	/**
 	 * @brief function to build the internal representation
 	 */
	virtual void buildImplementation(SearchTree *searchTree) = 0;

	virtual Variable *copy(SearchTree *searchTree) const = 0;


	// ishii
	void reset()
	{
		//TODO:
		//delete m_implementation;
		m_implementation = VarImplPtr();
	}

protected:
	// @var the name of the variable
	std::string m_name;

	// @var the domain of the variable
	Domain *m_domain;

	// @var the internal representation of the variable
	VarImplPtr m_implementation;

	/**
 	 * @var counter of the instantiated variables
 	 */
	static int count;

	// copy protection
	Variable(const Variable & right) {}
	Variable & operator=(const Variable & right) {}

private:
	void createAnonymousName(char *c, int n);
};


// Some of the implementations:

bool SearchTree::discardBox()
{
	m_heap->discardBox();
	return !m_heap->isEmpty();
}


template<class D>
inline void SearchTree::splitBox(long adr,
                                 const D & dom1,
                                 const D & dom2)
{
	if (m_dfs) {
		long numb = m_changeHeap->addBox(3 * sizeof(D));
		long indexDomainBT = m_changeHeap->allocate(sizeof(D), const_domain<D>(adr));
		m_current->split(adr, sizeof(D), dom1, dom2, numb, new DomainChange(numb, indexDomainBT));
	} else {
		splitBoxToFront<D>(adr, dom1, dom2);
	}
}

template<class D>
inline void SearchTree::splitBox(long adr,
                                 const D *doms,
                                 int n)
{
	if (m_dfs) {
		long numb = m_changeHeap->addBox((n + 1) * sizeof(D));
		long indexDomainBT = m_changeHeap->allocate(sizeof(D), const_domain<D>(adr));
		m_current->split(adr, sizeof(D), doms, n, numb, new DomainChange(numb, indexDomainBT));
	} else {
		// TODO
		//splitBoxToFront<D>(adr, doms, n);
	}
}

template<class D>
inline void SearchTree::reduce(long adr, const D & dom)
{
	long numb = m_changeHeap->addBox(2 * sizeof(D));
	long indexDomainBT = m_changeHeap->allocate(sizeof(D), const_domain<D>(adr));
	m_current->reduce(adr, sizeof(D), dom, numb, new DomainChange(numb, indexDomainBT));
	m_current->goChild(m_current->getChildren()[0]);
}

inline void SearchTree::prepareReduce()
{
	if (m_dfs) {
		m_current->prepareLargeReduce();
		m_current->goChild(m_current->getChildren()[0]);
	}
}

inline void Node::split(long indexDomain, size_t size, const Domain & dom1, const Domain & dom2, long numb, DomainChange *before)
{
	long indexDomainBT = m_tree->getChangeHeap()->allocate(size, dom1);
	this->addChild(new SplitNode(m_tree, indexDomain, size, new DomainChange(numb, indexDomainBT), before, this));
	indexDomainBT = m_tree->getChangeHeap()->allocate(size, dom2);
	this->addChild(new SplitNode(m_tree, indexDomain, size, new DomainChange(numb, indexDomainBT), before, this));
}


inline void Node::split(long indexDomain, size_t size, const Domain *dom, int n, long numb, DomainChange *before)
{
	long indexDomainBT;
	for (int i = 0; i < n; i++) {
		indexDomainBT = m_tree->getChangeHeap()->allocate(size, dom[i]);
		this->addChild(new SplitNode(m_tree, indexDomain, size, new DomainChange(numb, indexDomainBT), before, this));
	}
}

inline void Node::prepareLargeReduce()
{
	this->addChild(new ReduceNode(m_tree, this));
}

inline void Node::reduce(long indexDomain, size_t size, const Domain & dom1, long numb, DomainChange *before)
{
	long indexDomainBT = m_tree->getChangeHeap()->allocate(size, dom1);
	this->addChild(new SplitNode(m_tree, indexDomain, size, new DomainChange(numb, indexDomainBT), before, this));
}

inline bool Node::goChild(Node *n)
{
	bool find = false;
	unsigned int i = 0;
	while ((i < m_numChildren) && !find) {
		find = m_children[i] == n;
		++i;
	}
	if (find) {
		n->goHere();
		return true;
	} else {
		return false;
	}
}

inline bool Node::goChild(Node *n, Box *b)
{
	bool find = false;
	unsigned int i = 0;
	while ((i < m_numChildren) && !find) {
		find = m_children[i] == n;
		++i;
	}
	if (find) {
		n->goHere(b);
		return true;
	} else {
		return false;
	}
}

inline void Node::goAncestor(Node *parent)
{
	bool resultGoBack = true;
	while ((m_tree->getCurrent() != parent) && resultGoBack) {
		resultGoBack = goBack();
	}
}

END_NAMESPACE_ELISA

/**
 * Output operator for variable
 * @relates Variables
 */
inline std::ostream &
operator<<(std::ostream & os, const elisa::Variable & v)
{
	v.print(os);
	return os;
}

inline std::ostream &
operator<<(std::ostream & os, const elisa::VariableImpl & v)
{
	v.getSymbolicRep()->print(os);
	return os;
}

#endif // ELISA_VARIABLE_H
